package com.ds.seqlist;

import java.util.Arrays;

/**
 * 基于int的动态数组，根据元素的个数来动态调整数组大小
 * @author yuisama
 * @date 2022/04/17 10:07
 **/
public class MyArray {
    // 存放元素仍然还是int[]
    // data数组的长度我们可以让用户来指定
    private int[] data;
    // 表示当前动态数组中已经存储的元素个数
    private int size;

    public MyArray() {
        // 默认开辟10个大小的整型数组长度
        this(10);
    }

    public MyArray(int initCap) {
        this.data = new int[initCap];
    }

    /**
     * 在当前数组中添加一个新的元素val
     * @param val
     */
    public void add(int val) {
        data[size] = val;
        size ++;
        // 元素在添加的过程中，有可能把当前数组占满了~~
        // 如何知道当前data数组已满?
        if (size == data.length) {
            // 此时数组已满,扩容当前数组
            grow();
        }
    }

    /**
     * 在当前动态数组中index位置插入值为val的元素
     * @param index
     * @param val
     */
    public void add(int index,int val) {
        // 1.先判断边界条件，index是一个非法的索引
        // size是有效的元素个数 index == size
        // 插入时index = size，就是在数组尾部插入
        // index = 0，就是在数组头部插入，index = size就是在有效元素的尾部插入
        if (index < 0 || index > size) {
            // 错误输出
            System.err.println("add index illegal!");
            return;
        }
        // 从当前最后一个有效元素开始向后搬移元素，把index位置空出来
        for (int i = size - 1; i >= index; i--) {
            data[i + 1] = data[i];
        }
        // index位置空出来
        data[index] = val;
        size ++;
        // 判断数组是否已满
        if (size == data.length) {
            grow();
        }
    }

    /**
     * 查询当前动态数组中第一个值为val的元素对应的索引
     * 若不存在，返回 -1，表示当前val不存在
     * @param val
     * @return
     */
    public int getByValue(int val) {
        // 遍历当前的动态数组
        for (int i = 0; i < size; i++) {
            if (data[i] == val) {
                return i;
            }
        }
        // 还没找到val，不存在
        return -1;
    }

    /**
     * 判断当前动态数组中是否包含值为val的元素
     * @param val
     * @return
     */
    public boolean contains(int val) {
        int index = getByValue(val);
        return index != -1;
    }

    /**
     * 查询当前动态数组中索引为index的元素值
     * @param index
     * @return
     */
    public int get(int index) {
        // 1.判断index的合法性
        // size对应有效元素的下一个位置
        if (index < 0 || index >= size) {
            System.err.println("get index illegal!");
            return -1;
        }
        return data[index];
    }

    /**
     * 修改当前动态数组中索引为index位置的元素值为newVal，返回修改前的值
     * @param index
     * @param newVal
     * @return
     */
    public int set(int index,int newVal) {
        if (index < 0 || index >= size) {
            System.err.println("set index illegal!");
            return -1;
        }
        int oldVal = data[index];
        data[index] = newVal;
        return oldVal;
    }

    /**
     * 将动态数组中第一个值为oldVal的元素修改为newVal
     * @param oldVal
     * @param newVal
     * @return
     */
    public boolean setValue(int oldVal,int newVal) {
        int index = getByValue(oldVal);
        if (index != -1) {
            data[index] = newVal;
            return true;
        }
        System.err.println("old value is not exist!");
        return false;
    }

    /**
     * 删除索引为index对应的元素，返回删除前的元素值
     * @param index
     * @return
     */
    public int removeIndex(int index) {
        if (index < 0 || index >= size) {
            System.err.println("remove index illegal!");
            return -1;
        }
        // 元素搬移，从index开始，后一个元素覆盖前一个元素，一直走到size - 1(最后一个有效元素)
        // data[i] = data[i + 1]
        // 最后一个元素向前搬移 i + 1 == size - 1 => i < size - 1
        int oldVal = data[index];
        for (int i = index; i < size - 1; i++) {
            data[i] = data[i + 1];
        }
        size --;
        return oldVal;
    }

    public int removeFirst() {
        return removeIndex(0);
    }

    public int removeLast() {
        return removeIndex(size - 1);
    }

    /**
     * 删除当前动态数组中第一个值为val的元素，返回是否删除成功
     * @param val
     * @return
     */
    public boolean removeByValueOnce(int val) {
        for (int i = 0; i < size; i++) {
            if (data[i] == val) {
                // 此时i就是第一个值为val的元素
                removeIndex(i);
                return true;
            }
        }
        return false;
    }

    /**
     * 删除当前数组中所有值为val的元素
     * @param val
     * @return
     */
    public void removeAllValue(int val) {

        // TODO 留给大家思考一下，如何把当前数组中所有值为val的元素全部删了~~
//        for (int i = 0; i < size; i++) {
//            if (data[i]==val){
//                removeIndex(i);
//            }
//        }
        int fast;
        int slow=0;
        for (fast = 0; fast < size; fast++) {
            if (data[fast]!=val){
                data[slow++]=data[fast];
            }
        }
        size=slow;
    }

    public String toString() {
        String ret = "[";
        // 此时取得是有效数据，使用size属性
        // size表示当前有效元素的下一个索引位置
        for (int i = 0; i < size; i++) {
            ret += data[i];
            if (i != size - 1) {
                ret += ", ";
            }
        }
        ret += "]";
        return ret;
    }

    /**
     * 对于外部的使用者来说，压根都不知道你MyArray这个类中还有个int[]，数组的扩容对外部也是不可见的
     * 设置为private权限
     */
    private void grow() {
        // copyOf方法返回扩容后的新数组
        this.data = Arrays.copyOf(data,data.length * 2);
    }
}